#include <iostream>
using std::cout;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr)
        {
            ListNode* pre = cur->next;
            ListNode* back = pre->next;
            cur->next = back; // 步骤1
            pre->next = back->next; // 步骤2
            back->next = pre; // 步骤3

            cur = cur->next->next;
        }
        return dummyHead->next;
    }
};
int main(int argc, char const *argv[])
{
    ListNode *head = new ListNode();
    head->val = 1;
    head->next = nullptr;
    ListNode *cur = head;
    for (int i = 1; i < 5; ++i)
    {
        ListNode *newNode = new ListNode();
        newNode->next = nullptr;
        newNode->val = i + 1;
        cur->next = newNode;
        cur = newNode;
    }
    cur = head;
    #if 1
    while (cur)
    {
        if(cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
    #endif
    Solution s;
    cur = s.swapPairs(head);
    while (cur)
    {
        if(cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
    getchar();
    return 0;
}
